TRACKING AND REGRET BOUNDS FOR ONLINE ZEROTH-ORDER EUCLIDEAN AND RIEMANNIAN OPTIMIZATION

Abstract

We study numerical optimization algorithms that use zeroth-order information to minimize time-varying geodesically convex cost functions on Riemannian manifolds. In the Euclidean setting, zeroth-order algorithms have received a lot of attention in both the time-varying and time-invariant cases. However, the extension to Riemannian manifolds is much less developed. We focus on Hadamard manifolds, which are a special class of Riemannian manifolds with global nonpositive curvature that offer convenient grounds for the generalization of convexity notions. Specifically, we derive bounds on the expected instantaneous tracking error, and we provide algorithm parameter values that minimize the algor..